/**********************************************************************
**	Authors: Erik Sapir & Lior Zivi

**
** Fine-grained synchronization: lock coupling (hand-over-hand locking).
**
**
**********************************************************************/

#ifndef __FINE_LIST__H
#define __FINE_LIST__H

#include "framework/cpp_framework.h"
#include <memory>
#include "set.h"

using namespace CMDR;

template<typename T>
class FineList : public set<T> {

private:
	//list node
	class Node : public HazardMemory::Object {
	public:
		const T	m_item; //item stored in node
		VolatileType<Node*>	m_next; //next node in list
		CMDR::ReentrantLock m_lock; //synchronizes individual Node

		Node(const T& item) : m_item(item), m_next(null) { }
		Node(const T& item, Node* const next) : m_item(item), m_next(next) { }

		virtual ~Node() {;}

		virtual bool isValid() { return true; }
		virtual HazardMemory::Object* getNextValid(const int indx) {
			return m_next;
		}
		virtual HazardMemory::Object* getNextValid(const int indx, int& flag) {
				
			flag = 0; 
			return m_next;
		}

		//lock node
		void Lock()  { m_lock.lock(); }

		//unlock node
		void UnLock() { m_lock.unlock(); }
	};

private:

	VolatileType<Node*>				m_head; //First list entry
	SnapshotCounter					m_counter; // counter for number of element in the list

public:

	FineList(int numOfThreads) :  m_counter(numOfThreads) {
		printf("\n\tSet Is: Fine List\n");

		// Add sentinels to start and end
		m_head = new Node (Integer::MIN_VALUE, null);
		Node* tail = new Node(Integer::MAX_VALUE);
		m_head->m_next = tail;
	}

	//desctructor - removes all list elements
	~FineList(){
		//we assume no one access the object at this point.
		Node* curr = m_head;
		Node* next = null;

		//go ovel all list elements and delete them
		while(null != curr) {
			next = curr->m_next;
			delete curr;
			curr = next;
		}
	}

	bool add(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pred;
		HazardMemory::Ptr<Node> curr;
		HazardMemory::Ptr<Node> succ;
		bool returnValue;
	
		pred = m_head;

		pred->Lock();
				
		try {
			
			curr.extractNext(pred,0);
			curr->Lock();

			try {
				//find the first element equal or greater to the new element to be added.
				//do it using the hand-by-hand locking
				while(curr->m_item < item){
					pred->UnLock();
					succ.extractNext(curr,0);
					pred = curr;
					curr = succ;

					curr->Lock();
				}

				if (curr->m_item == item){
					//element aleady in list - nothing to add
					returnValue = false;
				}
				else {
					//add the new element to list
					std::auto_ptr<Node> node(new Node(item, curr.getReference()));
					pred->m_next = node.get();

					node.release();

					//added successfully - increment number of elements in list
					m_counter.inc(threadID);

					returnValue = true;	
				}
			}
			catch (const std::exception& ){
				returnValue = false;
			} 

			//always unlock
			curr->UnLock();
		}
		catch (const std::exception& ){
			returnValue = false;
		}

		//always unlock
		pred->UnLock();

		return returnValue;
	}

	bool remove(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pred;
		HazardMemory::Ptr<Node> curr;
		HazardMemory::Ptr<Node> succ;
		
		bool returnValue;

		pred = m_head;

		pred->Lock();
				
		try {
			
			curr.extractNext(pred,0);
			curr->Lock();

			try {
				//find the first element equal or greater to the new element to be removed.
				//do it using the hand-by-hand locking
				while(curr->m_item < item){
					pred->UnLock();
					succ.extractNext(curr,0);
					pred = curr;
					curr = succ;

					curr->Lock();
				}

				if (curr->m_item == item){
					//remove element from list
					succ.extractNext(curr, 0);				
					pred->m_next = succ.getReference();

					//retire node - will be acctually deleted when not used anymore
					curr.retire();

					//element removed successfully - decrement number of element in list
					m_counter.dec(threadID);

					returnValue = true;
				}
				else {
					//element not found in list - nothing to remove
					returnValue = false;	
				}
			}
			catch (const std::exception& ){
				returnValue = false;
			} 

			//always unlock
			curr->UnLock();
		}
		catch (const std::exception& ){
			returnValue = false;
		}

		//always unlock
		pred->UnLock();

		return returnValue; 
	}

	bool contains(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pred;
		HazardMemory::Ptr<Node> curr;
		HazardMemory::Ptr<Node> succ;
		
		bool returnValue;

		pred = m_head;

		pred->Lock();
				
		try {
			
			curr.extractNext(pred,0);
			curr->Lock();

			try {
				//find the first element equal or greater to the element we are searching.
				//do it using the hand-by-hand locking
				while(curr->m_item < item){
					pred->UnLock();
					succ.extractNext(curr,0);
					pred = curr;
					curr = succ;

					curr->Lock();
				}

				//return true iff element found in list
				if (curr->m_item == item){
					returnValue = true;
				}
				else {
					returnValue = false;	
				}
			}
			catch (const std::exception& ){
				returnValue = false;
			} 

			//always unlock
			curr->UnLock();
		}
		catch (const std::exception& ){
			returnValue = false;
		}

		//always unlock
		pred->UnLock();

		return returnValue; 
	}

	void clean(int threadID) {
		HazardMemory::Ptr<Node> head;
		HazardMemory::Ptr<Node> curr;

		head = m_head;

		//lock head - will remain locked untill end of function
		head->Lock();

		curr.extractNext(head, 0);
 
		//go over the list and remove all elements
		//in the list
		try {
			while(curr->m_item < Integer::MAX_VALUE) {
				curr->Lock();
				try {
					head->m_next = curr->m_next;

					//retire node - will be acctually deleted when not used anymore
					curr.retire();

					//element removed successfully - decrement number of elements in list
					m_counter.dec(threadID);
				}
				catch (const std::exception& ){}

				curr->UnLock();

				curr.extractNext(head, 0);
			}
		}
		catch (const std::exception& ){}
 
		//unlock head
		head->UnLock();
	}
	
	bool isEmpty(int threadID) {
		HazardMemory::Ptr<Node> head;
		HazardMemory::Ptr<Node> succ;
		
		bool returnValue;

		head = m_head;

		//lock head
		head->Lock();

		try {
			succ.extractNext(head, 0);

			//lock the node that pointing to
			succ->Lock();

			//if head is pointing to tail, than list in empty
			try {
				returnValue = (succ->m_item == Integer::MAX_VALUE);
			}
			catch (const std::exception& ){}

			succ->UnLock();
		}
		catch (const std::exception& ){}
 
		//unlock head
		head->UnLock();

		return returnValue;
	}
	
	int size(int threadID){
		return m_counter.scan();
	}

private:

}; 

#endif // __FINE_LIST__H
